package leetcode.code1361;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	class Union {

		public int n;
		public int[] root;
		public int[] sizes;
		public int[] stack;
		public int[] parent;
		public int rootSize;

		public Union(int n) {
			this.n = n;
			this.rootSize = n;
			this.root = new int[n];
			this.sizes = new int[n];
			this.stack = new int[n];
			this.parent = new int[n];
			for (int i = 0; i < n; i++) {
				root[i] = i;
				sizes[i] = 1;
				parent[i] = -1;
			}
		}

		public int findRoot(int num) {
			int root = this.root[num];
			int p = -1;
			while (root != num) {
				this.stack[++p] = num;
				num = root;
				root = this.root[num];
			}
			while (p > -1) {
				num = stack[p--];
				this.root[num] = root;
			}
			return root;
		}

		public boolean isSameSet(int num1, int num2) {
			return this.findRoot(num1) == this.findRoot(num2);
		}

		public boolean union(int num1, int num2) {
			// this.parent[num2] != -1 说明有两个父节点 this.parent[num1] == num2 双向
			if (this.parent[num2] != -1 || this.parent[num1] == num2) {
				return false;
			}
			this.parent[num2] = num1;
			int p1 = this.findRoot(num1);
			int p2 = this.findRoot(num2);
			if (p1 != p2) {
				int size1 = this.sizes[p1];
				int size2 = this.sizes[p2];
				if (size1 < size2) {
					this.root[p1] = p2;
					this.sizes[p2] += size1;
					this.sizes[p1] = 0;
				} else {
					this.root[p2] = p1;
					this.sizes[p1] += size2;
					this.sizes[p2] = 0;
				}
				this.rootSize--;
			}
			return true;
		}

	}

	public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
		Union union = new Union(n);
		for (int i = 0; i < n; i++) {
			int left = leftChild[i];
			if (left != -1 && !union.union(i, left)) {
				return false;
			}
			int right = rightChild[i];
			if (right != -1 && !union.union(i, right)) {
				return false;
			}
		}
//		H.printObject(union.parent);
//		if(union.rootSize == 1)H.printObject(union.root);
//		H.printObject(union.rootSize);
		return union.rootSize == 1;// 必须有一个根
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug4();
		so.debug3();
		so.debug1();
		so.debug2();
	}

	@Override
	public void debug1() {
		HelpDebug.compare(false, this.validateBinaryTreeNodes(4, HelpDebug.str2array3("[1,0,3,-1]"), HelpDebug.str2array3("[-1,-1,-1,-1]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(true, this.validateBinaryTreeNodes(4, HelpDebug.str2array3("[1,-1,3,-1]"), HelpDebug.str2array3("[2,-1,-1,-1]")));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(false, this.validateBinaryTreeNodes(4, HelpDebug.str2array3("[1,2,0,-1]"), HelpDebug.str2array3("[-1,-1,-1,-1]")));

	}

	@Override
	public void debug4() {
		HelpDebug.compare(false, this.validateBinaryTreeNodes(2, HelpDebug.str2array3("[1,0]"), HelpDebug.str2array3("[-1,-1]")));

	}

}
